1. Field of the Invention
The present invention relates to a meshing method, particularly to a method for generating a quadrilateral mesh from a triangular mesh.
2. Description of Background Art
Meshing or mesh generation is a process for dividing a geometric model generated, for example, by a Computer Aided Design (CAD) tool into a set of small elements. The mesh may be a two-dimensional mesh, such as a triangular mesh or quadrilateral mesh. In computer simulation, such as an analysis of a car crash, a triangular mesh typically cannot provide a reliable solution. Accordingly, a quadrilateral mesh is often employed. On the other hand, automatic generation of the triangular mesh, technologies such as a bubble mesh method described in Japanese Unexamined Patent Publication No. Hei 7-230487 and 8-315183 are established. Yet, automatic generation of a quadrilateral mesh is seldom practical. Therefore, in most cases a quadrilateral mesh is generated by a technique which involves tremendous manual work, such as several months for CAD data of an automobile.
Thus, there is a great demand for a technique for automatic generation of the quadrilateral mesh. In addition, it is desirable that the technique satisfy the following requirements:
(1) minimal distortion in generated quadrilateral elements; In an analysis by calculation dynamics, an extremely long and slender element or an element with an extremely large (or small) angle affects badly on the result of the analysis; therefore, ideally, it is desirable that the shape of every quadrilateral element be as close to a square as possible. PA1 (2) the alignment directions of generated quadrilateral elements can be controlled; in an analysis by calculation dynamics, it is often desirable to have elements aligned along a specific direction, such as a direction corresponding to a stress or a direction of a boundary of geometric model regions; therefore, the generation of a mesh in which many elements are regularly aligned in a direction specified by a user is desired. PA1 (3) distribution of sizes of elements can be controlled; it is desirable to generate fine mesh elements in an important part and rough mesh elements in a less important part from a viewpoint of reducing the calculation volume; a sudden change of sizes of elements, however, generates a T structure (a state where a node of an adjacent element is on a chord) which badly affects the analysis. Thus, it is important to give distribution to sizes of mesh elements while assuring that each element is connected by a mutually shared node plus a chord; PA1 (4) a complex curved-surface geometric model can be covered; there are various curved surfaces in a geometric model designed by CAD tools, such as a trim curved surface acquired by excising a part of a curved region or an extremely winding curved surface; it is desirable that a quadrilateral mesh can be automatically generated even on such a curved-surface geometric model. PA1 (1) a technique to convert pairs of adjacent triangular elements into quadrilateral elements in order from a pair which makes a square close to a perfect square (See Lo. S. H., "Generating Quadrilateral Elements on Plane and Over Curved Surfaces," Computer and Structures, Vol. 31, No. 3, pp. 421-426, 1989, or Borouochaki H., Frey P. J., and George P. L., "Unstructured Triangle-Quadrilateral Mesh Generation, Application to Surface Meshing," Proceedings of 5th International Meshing Roundtable, pp. 299-242, 1996); while consideration is given to improvement of geometrical regularity (generating a quadrilateral element closer to a perfect square), the viewpoints of control of alignment directions (generating a quadrilateral element comprising edges which make a small angle with a specified alignment direction) and improvement of topological regularity (decreasing isolated triangular elements and converting as many triangular elements as possible to quadrilateral elements) are not considered. PA1 (2) a technique wherein, while constantly managing the number of adjacent unprocessed triangular elements (N.sub.t) for each triangular element, triangular elements are ranked by N.sub.t and the triangular elements whose N.sub.t equals to 1 are preferentially made into pairs and converted into quadrilateral elements (See Heighway E. A., "A Mesh Generator for Automatically Subdividing Irregular Polygons into Quadrilaterals," IEEE Transactions on Magnetics, Mag-19, pp. 2535-2538, 1983. Or Johnston B. P., Sullivan J. M., and Kwasnik A., "Automatic Conversion of Triangle Finite Element Meshes to Quadrilateral Elements," International Journal for Numerical Methods in Engineering, Vol. 31, pp. 67-84, 1991); the improvement of the topological regularity is considered and a mesh with a small number of the triangular elements is generated, the improvement of the geometrical regularity and the control of the alignment directions are not considered. PA1 (3) a technique wherein triangular elements are grouped into several bandlike areas, and in such groups, as many adjacent triangular elements as possible are made into pairs (See the references cited in group (1) above; it is a technique aiming at the improvement of the topological regularity and the control of the alignment directions. However, it does not always lead to good results since it cannot always make appropriate bandlike areas. Also, the results may be very different depending on implementation because processing order of triangular elements is not unique.
The following bubble-mesh technique may be used to generate a quadrilateral mesh. The four lowest potential points are aligned in a cross shape surrounding the center of a spherical object, the attraction to the surrounding spherical objects is defined in a direction of the lowest potential points, by means of dynamic simulation, an object to be meshed is filled with the spherical objects, and the center of the spherical object is used as a node (see pp.7-12 of "Automated Well-shaped Quadrilateral Mesh Generation Using the Squarely-packing Bubble Mesh Method," Information Processing Graphics and CAD Study Report 96-CG-87, 1997 by Itoh, Yamada, Inoue, Shimada and Furuhata).
The above method has a shortcoming that, when adjacent spherical objects are accidentally located in the middle point of two lowest potential points, attraction to the lowest potential points becomes balanced and they get fixed being unable to move to an optimal location. Moreover, such a method employs spherical objects (circular or spherical bubbles).
On the other hand, technology has been developed for converting a triangular mesh to a quadrilateral mesh that removes a shared edge of triangular elements in certain order for a pair of adjacent triangular elements to convert them into one quadrilateral element. When this process is complete, most of the triangular elements are converted into the quadrilateral elements, and a quadrilateral mesh comprising the quadrilateral elements and a few of the triangular elements is generated. In the event that a quadrilateral mesh comprising only the quadrilateral elements is required, a technique for converting triangular and quadrilateral elements into quadrilateral elements of half the size is used (Literature 1: Shimada K., and Itoh T., Automated Conversion of 2D Triangular Mesh into Quadrilateral Mesh, International Conference on Computational Engineering Science '95 Proceedings, pp. 350-355, 1995). The quality of the quadrilateral mesh generated in this conversion is determined in order of converting pairs of adjacent triangular elements. In addition, the order of converting pairs of adjacent triangular elements may be classified into the following three types.